package l.l.w.CodingInterviews;

/**
 * Created by llw on 2018/3/5.
 *删除链表的节点（在O(1)时间复杂度下）
 */
public class _18Problem {
    /**
     * 给定链表的头结点和节点p，从链表中删除节点p、
     *      时间复杂度为O(1)
     *      如果head和p为null，则直接返回（输入数据校验）
     *      如果删除的是头结点，则直接head= head.next即可
     *      如果待删除的节点不是尾节点，则直接将p.next的值复制给p，然后删除p.next即可。
     *      如果待删除的节点为尾节点，则需要从头遍历，找到p的前驱节点，然后删除。
     * @param head
     * @param p
     */
    public void deleteNode(ListNode head, ListNode p){
        if(head == null || p == null) return;
        if(head == p) {
            head = head.next;
            return;
        }
        if(p.next != null){
            p.val = p.next.val;
            p.next = p.next.next;
        }else{
            ListNode cur = head;
            while(cur.next != p){
                cur = cur.next;
            }
            cur.next = null;
        }
    }
}
